Qu'est-ce que spanning tree ?

En informatique, un "spanning tree" (arbre couvrant en français) est un sous-graph d'un graphe non orienté qui inclut tous les sommets du graphe d'origine tout en formant un arbre, c'est-à-dire sans cycle.

Dans le domaine des réseaux informatiques, le "spanning tree" est une technique utilisée pour éviter la formation de boucles dans les topologies en arbre de réseau. Ces boucles peuvent causer des problèmes de redondance, de ralentissement et de surcharge du réseau. Le "spanning tree" élimine ces boucles en désactivant certains liens de données dans le réseau, de sorte qu'il ne reste qu'un seul chemin pour relier tous les nœuds du réseau.

Le processus de calcul de l'arbre couvrant se fait grâce à un algorithme qui sélectionne un nœud racine, puis explore l'ensemble des voisins de ce nœud, en choisissant les arêtes qui ne forment pas de cycle. Cette opération est répétée jusqu'à ce que tous les nœuds du graphe soient couverts.

Le "spanning tree" est utilisé dans de nombreuses normes de réseaux locaux (LAN) telles que le protocole Spanning Tree Protocol (STP) ou le Rapid Spanning Tree Protocol (RSTP).